#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        std::vector<std::vector<int>> ans;

        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            long long x = nums[i];

            if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;

            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                long long y = nums[j];

                if (x + y + nums[j + 1] + nums[j + 2] > target) break;
                if (x + y + nums[n - 2] + nums[n - 1] < target) continue;

                int k = j + 1;
                int l = n - 1;

                while (k < l) {
                    long long sum = x + y + nums[k] + nums[l];
                    if (sum < target) {
                        ++k;
                    }
                    else if (sum > target) {
                        --l;
                    }
                    else {
                        ans.emplace_back(std::vector<int>{nums[i], nums[j], nums[k], nums[l]});
                        while (k < l && nums[k] == nums[k + 1]) ++k;
                        while (k < l && nums[l] == nums[l - 1]) --l;
                        ++k;
                        --l;
                    }
                }
            }
        }
        return ans;
    }
};

int main() {
    std::vector<int> nums = { 1, 0, -1, 0, -2, 2 };
    int target = 0;
    Solution sol;
    std::vector<std::vector<int>> result = sol.fourSum(nums, target);
    std::cout << "Test Case 3: Array with valid quadruplets" << std::endl;
    std::cout << "Result size: " << result.size() << std::endl;
    for (const auto& quad : result) {
        for (int num : quad) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}